package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
 * <p>
 * We are given an array A of positive integers, and two positive integers L and R (L <= R).
 * <p>
 * Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.
 * <p>
 * 一开始想到滑动窗口思路, 好像有点问题, 改为dp思路:
 * dp思路1: dp[i]=从0到i范围内所有合法子数组个数 X
 * dp思路1: dp[i]=以i为结尾的所有合法子数组个数 X
 * todo 第一次dp题答案是dp数组加和的
 */
public class LC795_1  implements Unknown {
    /**
     * Example :
     * Input:
     * A = [2, 1, 4, 3]
     * L = 2
     * R = 3
     * Output: 3
     * Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
     * <p>
     * 22243
     * 222143
     * 错误写法
     */
    public int numSubarrayBoundedMax(int[] A, int L, int R) {
        int[] dp = new int[A.length];
        dp[0] = A[0] >= L && A[0] <= R ? 1 : 0;
        int total = dp[0];
        for (int i = 1; i < A.length; i++) {
            if (A[i] > R) {
                dp[i] = 0;
            } else if (A[i] < L) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 1] + 1;
            }
            total += dp[i];
        }
        System.out.println(Arrays.toString(dp));
        return total;
    }

    public static void main(String[] args) {
//        int[] a = new int[]{2, 2, 2, 2, 1, 4, 3};
//        System.out.println(new LC795_1().numSubarrayBoundedMax(a, 2, 3));
        //32
        //69
        int[] a = new int[]{73, 55, 36, 5, 55, 14, 9, 7, 72, 52};
        System.out.println(new LC795_1().numSubarrayBoundedMax(a, 32, 69));//正确答案22
    }
}
